Today, users use various types of client apparatuses (for example, computers, mobile terminals, and so on). By operating such client apparatuses, the users are able to access a server apparatus on a network, and use services provided by the server apparatus. For example, there is a service called a social network service (SNS). The SNS connects multiple users through a network, and helps the users to interact with each other.
On SNS, users transmit information to other already connected users by operating their client apparatuses. For example, a first user transmits information indicating that the first user likes certain content on a Web page to a server apparatus from his client apparatus. Then, the server apparatus transmits information indicating that the first user likes the content to a second user who is connected to the first user. If the second user who has received the information also likes the content, the second user may transmit such information to a third user in the same way. Thus, the information may be transmitted to users who are not directly connected to the first user who originated the information. The users are able to increase the number of recipients of information by making more connections with other users.
Meanwhile, there has been proposed a method of analyzing communication of information based on connections between users on SNS. For example, connections between users may be represented by a graph in which users are represented as nodes and connections between the users are represented as edges (lines connecting the nodes). By performing predetermined operations using an adjacency matrix representing such a graph, an indicator called Random Walk with Restart (RWR) is calculated. The RWR is an indicator representing the probability that, when information is transmitted from a starting node through a random path along the edges, the information reaches an end node of interest. For example, there has been proposed a method of tracking changes in the RWRs between the nodes specified by the user, in the case where edges are added as time passes. This method performs a fast update of data used for approximate calculation of the RWRs between the specified nodes, only for a small number of added edges.
Examples of the related art are disclosed in:
Jia-Yu Pan et al, “Automatic Multimedia Cross-modal Correlation Discovery”, Proceedings of SIGKDD 2004, ACM SIGKDD, 2004; and
Hanghang Tong et al., “Proximity Tracking on Time-Evolving Bipartite Graphs”, Proceedings of SDM2008, SIAM, 2008, p. 704-715.
New connections are made between information entities (for example, users) as time passes. This is represented as addition of edges between the nodes in a graph. For example, when an edge is added between first and second nodes representing first and second information entities, this indicates that direct communication between the first and second information entities is enabled. If the second information entity has an existing connection to a third information entity, information originated from the first information entity is more likely to be transmitted to the third information entity and other information entities therearound through the second information entity. That is, addition of a small number of edges may significantly increase the communication range which has been only locally established.